#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#include "DList.h"

//创建新节点
//void NewDListNode(DataType data)
Node* NewDListNode(DataType data) // 新节点的返回值的Node*,是一个结构体
{
    Node* newNode = (Node*)malloc(sizeof(Node*)); //创建新节点需要开辟空间，类型和大小都是Node*
    if(NULL == newNode) //malloc出来的空间需要检测
    {
        assert(0);
        return NULL;
    }

    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;

    return newNode; //要返回节点
}


//初始化
void DListInit(Node** head)
{
    assert(head);

    *head = NewDListNode(0); //给出头节点，里面的数任意给
    (*head)->next = NULL;
}

//尾插
void DListPushBack(Node* head, DataType data)
{
    assert(head);

    //先找到最后一个节点
    Node* temp = head; //temp的作用是防止head走到最后一个节点。如果后面还要用head，而此时head已经走到最后一个节点，而自己可能会忽略这一点。
    Node* cur = NULL;
    while(temp)
    {
        cur = temp;
        temp = temp->next;
    }//此时的cur节点就是最后一个节点

    Node* newNode = NewDListNode(data);

    newNode->prev = cur;
    newNode->next = NULL;
    cur->next = newNode;
}

//尾删
void DListPopBack(Node* head)
{
    assert(head);

    //只有头结点
    if(NULL == head->next)
        return;


    //需要知道最后一个节点和最后一个节点的前一个节点
    Node* cur = head->next;
    Node* pre = head;
    while(cur->next)
    {
        pre = cur;
        cur = cur->next;
    }
    free(cur);
    pre->next = NULL;
}

//头插
void DListPushFront(Node* head, DataType data)
{
    assert(head);

    Node* newNode = NewDListNode(data);

    Node* cur = head->next;
    newNode->prev = head;
    newNode->next = cur;
    cur->prev = newNode;
    head->next = newNode;
}

//头删
void DListPopFront(Node* head)
{
    assert(head);

    if(NULL == head->next) //只有头节点
        return;
    
    else if(NULL == head->next->next) //只有一个元素
    {
        free(head->next);
        head->next =NULL;
    }
    else  //多个元素（大于等于2）
    {
        Node* cur = head->next;

        head->next = cur->next;
        cur->next->prev = head;

        free(cur);
    }
}

//双向链表可插在pos位置之前，也可插在pos位置之后,只需要写一个就可以了
//双链表一般是在pos位置之前插

//任意位置的插入(在pos的后一位插入)
//void DListInsert(Node* pos, DataType data)
//{
//    Node* newNode = NULL;
//
//    if(NULL == pos)
//        return;
//    
//    newNode = NewDListNode(data);
//    newNode->prev = pos;
//    newNode->next = pos->next;
//    pos->prev = newNode;
//    pos->next = newNode;
//}

//在pos之前插入(插入的元素在pos位置)
void DListInsert1(Node* pos, DataType data)
{
    Node* newNode = NULL;

    if(NULL == pos)
        return;

    newNode = NewDListNode(data);
    newNode->prev = pos->prev;
    newNode->next = pos;
    pos->prev->next = newNode;
    pos->prev = newNode;
}
//任意位置的删除(pos位置的删除)
void DListErase(Node* pos)
{
    if(NULL == pos)
        return;

    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;

    free(pos);
}

//获得有效元素的大小
int DListSize(Node* head)
{
    Node* cur = head->next;

    int count = 0;
    while(NULL != cur)
    {
        count++;
        cur = cur->next;
    }
   return count;
}

//查找
Node* DListFind(Node* head, DataType data)//查找的返回值是节点
{
    assert(head);

    Node* cur = head->next;
    while(cur)
    {
        if(data == cur->data)
            return cur;
        cur = cur->next;
    }
    return NULL; //没有找到节点则返回空
}

//判空
int DListEmpty(Node* head)
{
    assert(head);

    head->next = NULL;
}


//销毁
void DListDestroy(Node** head)
{
    Node* cur = NULL;
    Node* pre = NULL;

    cur = (*head)->next;
    pre = *head;

    while(NULL != cur)
    {
        pre = cur;
        free(pre);
        cur = cur->next;
    }
    free(*head);
    *head = NULL;
}

//打印
void DListPrint(Node* head)
{
    assert(head);

    if(NULL == head->next)
        return;
    Node* cur = head->next;
    while(cur)
    {
        printf("%d--->",cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}
